﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GrafosWindows.Model
{
    public class Grafo
    {
        private int[,] _matrizAdjascencia;
        public int[,] MatrizAdjascencia
        {
            get { return _matrizAdjascencia; }
            set { _matrizAdjascencia = value; }
        }

        private List<Vertice> _listaVertices;
        public List<Vertice> ListaVertices
        {
            get { return _listaVertices; }
            set { _listaVertices = value; }
        }

        private Dictionary<string, Vertice> _hashVertices;
        public Dictionary<string, Vertice> HashVertices
        {
            get { return _hashVertices; }
            set { _hashVertices = value; }
        }

        private List<Aresta> _listaArestas;
        public List<Aresta> ListaArestas
        {
            get { return _listaArestas; }
            set { _listaArestas = value; }
        }

        private Dictionary<string, Aresta> _hashArestas;
        public Dictionary<string, Aresta> HashArestas
        {
            get { return _hashArestas; }
            set { _hashArestas = value; }
        }

        private int _cardinalidade;
        public int Cardinalidade
        {
            get 
            {
                if (_cardinalidade == 0)
                {
                    return ListaVertices.Count;
                }
                return _cardinalidade; 
            }
            set { _cardinalidade = value; }
        }

        public Grafo()
        {
            Cardinalidade = 0;

            ListaVertices = new List<Vertice>();
            ListaArestas = new List<Aresta>();

            HashVertices = new Dictionary<string, Vertice>();
            HashArestas = new Dictionary<string, Aresta>();
        }

        public Grafo(string[] arquivo)
        {
            //Primeira linha do arquivo deve corresponder à cardinalidade do Grafo
            Cardinalidade = int.Parse(arquivo[0]);

            ListaVertices = new List<Vertice>();
            ListaArestas = new List<Aresta>();

            MatrizAdjascencia = new int[Cardinalidade, Cardinalidade];

            HashVertices = new Dictionary<string, Vertice>();
            HashArestas = new Dictionary<string, Aresta>();

            for (int i = 1; i <= Cardinalidade; i++)
            {
                Vertice node = new Vertice("V"+i);

                string[] parameters = arquivo[i].Split(' ');

                for (int j = 0; j < Cardinalidade; j++)
                {
                    MatrizAdjascencia[i - 1, j] = int.Parse(parameters[j]);
                }

                HashVertices.Add("V" + i, node);
                ListaVertices.Add(node);
            }

            for (int i = 0; i < MatrizAdjascencia.GetLength(0); i++)
            {
                for (int j = 0; j < MatrizAdjascencia.GetLength(1); j++)
                {
                    if (MatrizAdjascencia[i, j] > 0)
                    {
                        Vertice u = HashVertices["V" + (i + 1)];
                        Vertice v = HashVertices["V" + (j + 1)];

                        int peso = MatrizAdjascencia[i, j];

                        if (!HashArestas.ContainsKey(u.Name + v.Name) && !HashArestas.ContainsKey(v.Name + u.Name))
                        {
                            Aresta aresta = new Aresta(u, v, peso);

                            u.Vizinhos.Add(v);
                            u.Arestas.Add(aresta);
                            v.Vizinhos.Add(u);
                            v.Arestas.Add(aresta);

                            HashArestas.Add(u.Name + v.Name, aresta);
                            ListaArestas.Add(aresta);
                        }
                    }
                }
            }
        }

        public bool ExisteCaminho(string v, string u)
        {
            return ExisteCaminho(HashVertices[v], HashVertices[u]);
        }

        public bool ExisteCaminho(Vertice v, Vertice u)
        {
            return Caminho(v, u).Count > 0;
        }

        public List<Vertice> CaminhoDijkstra(Vertice v, Vertice u)
        {
            List<Vertice> caminho = new List<Vertice>();

            if (v.Equals(u))
            {
                caminho.Add(v);
                return caminho;
            }

            MetodoDijkstra(v);

            if (u.Antecessor != null)
            {
                caminho.Add(u);
                Vertice atual = u.Antecessor;
                while (!atual.Equals(v))
                {
                    caminho.Add(atual);
                    atual = atual.Antecessor;
                }
                caminho.Add(v);
            }

            return caminho;
        }

        public Grafo ArvoreMinima()
        {
            Grafo grafo = new Grafo();

            List<Vertice> novaListaVertices = new List<Vertice>();
            List<Aresta> listaArestasCopia = CopiaListaAresta();
            List<Aresta> novaListaArestas = new List<Aresta>();

            while (listaArestasCopia.Count > 0)
            {
                grafo.atualizarListaVizinho();

                Aresta menor = RemoverMenorAresta(listaArestasCopia);
                Vertice v = menor.V;
                Vertice u = menor.U;

                if (grafo.HashVertices.ContainsKey(v.Name) && grafo.HashVertices.ContainsKey(u.Name))
                {
                    bool caminho = grafo.ExisteCaminho(u.Name, v.Name);
                    if (!caminho)
                    {
                        grafo.adicionarAresta(menor);
                    }
                }
                else
                {
                    Vertice existente = null;
                    if (grafo.HashVertices.ContainsKey(v.Name))
                    {
                        existente = grafo.HashVertices[v.Name];
                        grafo.adicionarVertice(u);
                        grafo.adicionarAresta(menor);
                    }
                    if (grafo.HashVertices.ContainsKey(u.Name))
                    {
                        existente = grafo.HashVertices[u.Name];
                        grafo.adicionarVertice(v);
                        grafo.adicionarAresta(menor);
                    }

                    if (existente == null)
                    {
                        grafo.adicionarVertice(u);
                        grafo.adicionarVertice(v);
                        grafo.adicionarAresta(menor);
                    }
                }
            }

            foreach (Vertice vertice in ListaVertices)
            {
                if (!grafo.HashVertices.ContainsKey(vertice.Name))
                {
                    grafo.adicionarVertice(vertice);
                }
            }

            return grafo;
        }

        public Grafo ArvoreDijkstra(Vertice v)
        {
            MetodoDijkstra(v);
            Grafo grafo = new Grafo();

            List<Vertice> novaListaVertices = new List<Vertice>();
            List<Aresta> novaListaArestas = new List<Aresta>();

            foreach (Vertice vertice in ListaVertices)
            {
                Vertice novoVertice = new Vertice();
                novoVertice.Name = vertice.Name;
                novoVertice.Posicao = vertice.Posicao;

                if (vertice.Antecessor != null)
                {
                    Aresta novaAresta = null;
                    if (HashArestas.ContainsKey(vertice.Name + "" + vertice.Antecessor.Name))
                    {
                        novaAresta = HashArestas[vertice.Name + "" + vertice.Antecessor.Name];
                    }
                    else
                    {
                        novaAresta = HashArestas[vertice.Antecessor.Name + "" + vertice.Name];
                    }
                    novaListaArestas.Add(novaAresta);
                }
                novaListaVertices.Add(novoVertice);
            }

            grafo.ListaVertices = novaListaVertices;
            grafo.Cardinalidade = novaListaVertices.Count;
            grafo.ListaArestas = novaListaArestas;

            return grafo;
        }

        private void MetodoDijkstra(Vertice v)
        {
            foreach (Vertice vertice in ListaVertices)
            {
                vertice.Antecessor = null;
                vertice.Distancia = int.MaxValue;
                vertice.DistanciaAcumulado = int.MaxValue;
                vertice.Cor = Vertice.Cores.BRANCO;
            }

            v.Distancia = 0;
            v.Cor = Vertice.Cores.CINZA;

            List<Vertice> listaVerticesFinais = new List<Vertice>();
            List<Vertice> verticesNaoVisitados = CopiaListaVertices();

            while (listaVerticesFinais.Count < ListaVertices.Count)
            {
                Vertice atual = RemoverMenorVertice(verticesNaoVisitados);
                listaVerticesFinais.Add(atual);
                atual.Cor = Vertice.Cores.CINZA;

                foreach (Aresta aresta in atual.Arestas)
                {
                    Vertice vizinho = null;
                    if (aresta.U.Equals(atual))
                    {
                        vizinho = aresta.V;
                    }
                    else
                    {
                        vizinho = aresta.U;
                    }

                    if (vizinho.Cor == Vertice.Cores.BRANCO &&
                        (atual.Distancia + aresta.Peso) < vizinho.DistanciaAcumulado)
                    {
                        vizinho.DistanciaAcumulado = atual.Distancia + aresta.Peso;
                        vizinho.Distancia = atual.Distancia + aresta.Peso;
                        vizinho.Antecessor = atual;
                    }
                }
            }
        }

        public List<Vertice> Caminho(Vertice v, Vertice u)
        {
            List<Vertice> caminho = new List<Vertice>();

            if (v.Equals(u))
            {
                caminho.Add(v);
                return caminho;
            }

            MetodoBFS(v);

            if (u.Antecessor != null)
            {
                caminho.Add(u);
                Vertice atual = u.Antecessor;
                while (!atual.Equals(v))
                {
                    caminho.Add(atual);
                    atual = atual.Antecessor;
                }
                caminho.Add(v);
            }

            return caminho;
        }

        private void MetodoBFS(Vertice v)
        {
            foreach (Vertice vertice in ListaVertices)
            {
                vertice.Cor = Vertice.Cores.BRANCO;
                vertice.Antecessor = null;
                vertice.Distancia = int.MaxValue;
            }

            Queue<Vertice> fronteira = new Queue<Vertice>();
            v.Cor = Vertice.Cores.CINZA;
            v.Distancia = 0;

            fronteira.Enqueue(v);

            while (fronteira.Count > 0)
            {
                Vertice atual = fronteira.Dequeue();

                foreach (Vertice vizinho in atual.Vizinhos)
                {
                    if (vizinho.Cor == Vertice.Cores.BRANCO)
                    {
                        vizinho.Cor = Vertice.Cores.CINZA;
                        vizinho.Antecessor = atual;
                        vizinho.Distancia = atual.Distancia + 1;

                        fronteira.Enqueue(vizinho);
                    }
                }

                atual.Cor = Vertice.Cores.PRETO;
            }
        }

        private List<Vertice> CopiaListaVertices()
        {
            List<Vertice> copia = new List<Vertice>();

            foreach(Vertice vertice in ListaVertices)
            {
                copia.Add(vertice);
            }

            return copia;
        }

        private List<Aresta> CopiaListaAresta()
        {
            List<Aresta> copia = new List<Aresta>();

            foreach (Aresta aresta in ListaArestas)
            {
                copia.Add(aresta);
            }

            return copia;
        }

        private Vertice RemoverMenorVertice(List<Vertice> lista)
        {
            Vertice menor = lista[0];

            foreach (Vertice vertice in lista)
            {
                if (menor.Distancia > vertice.Distancia)
                {
                    menor = vertice;
                }
            }

            lista.Remove(menor);

            return menor;
        }

        private Aresta RemoverMenorAresta(List<Aresta> lista)
        {
            Aresta menor = lista[0];

            foreach (Aresta vertice in lista)
            {
                if (menor.Peso > vertice.Peso)
                {
                    menor = vertice;
                }
            }

            lista.Remove(menor);

            return menor;
        }

        private void atualizarListaVizinho()
        {
            foreach (Vertice vertice in ListaVertices)
            {
                vertice.Vizinhos.Clear();
            }

            foreach (Aresta aresta in ListaArestas)
            {
                Vertice u = aresta.U;
                Vertice v = aresta.V;

                u.Vizinhos.Add(v);
                v.Vizinhos.Add(u);
            }
        }

        public void adicionarAresta(Aresta aresta)
        {
            ListaArestas.Add(aresta);
            HashArestas.Add(aresta.U.Name + "" + aresta.V.Name, aresta);
        }

        public void adicionarVertice(Vertice vertice)
        {
            ListaVertices.Add(vertice);
            HashVertices.Add(vertice.Name, vertice);
        }
    }
}
